public class Main {

/**
 * 倒置字符串
 */
//    import java.util.Scanner;
//
//    // 注意类名必须为 Main, 不要有任何 package xxx 信息
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextLine()) { // 注意 while 处理多个 case
//                String input = in.nextLine();
//                //去掉最后的.
//                int n = input.length() - 1;
//                String s = input.substring(0, n);
//                //划分字符串
//                String[] ss = s.split(" ");
//                StringBuffer sb = new StringBuffer();
//                sb.append(ss[ss.length - 1]);
//                sb.append(".");
//                for(int i = ss.length - 2; i >=0; i--) {
//                    sb.append(" ");
//                    sb.append(ss[i]);
//                }
//                System.out.println(sb.toString());
//            }
//        }
//    }

/**
 * 买卖股票2
  */
//    import java.util.Scanner;
//
//    // 注意类名必须为 Main, 不要有任何 package xxx 信息
//    public class Main {
//        public static void main(String[] args) {
//            //贪心: 只要今天比昨天高 就+
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextInt()) { // 注意 while 处理多个 case
//                int n = in.nextInt();
//                int[] price = new int[n];
//                for(int i = 0; i < n; i++) {
//                    price[i] = in.nextInt();
//                }
//                int ret = 0;
//                for(int i = 1;  i < n; i++) {
//                    if(price[i] > price[i - 1]) {
//                        ret += price[i] - price[i - 1];
//                    }
//                }
//                System.out.println(ret);
//            }
//        }
//    }
    /**
     * 两个链表的公共节点
     */
//    import java.util.Scanner;
//
//    // 注意类名必须为 Main, 不要有任何 package xxx 信息
//    public class Solution {
//        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//            //先获取到链表的长度
//            ListNode cur1 = pHead1;
//            ListNode cur2 = pHead2;
//            int n = 0;
//            while (cur1 != null) {
//                n++;
//                cur1 = cur1.next;
//            }
//            int m  = 0;
//            while (cur2 != null) {
//                m++;
//                cur2 = cur2.next;
//            }
//            cur1 = pHead1;
//            cur2 = pHead2;
//            //先让较长的链表上的指针走他们两的差值
//            int step = Math.abs(m - n);
//            while (step > 0) {
//                if (m > n) {
//                    if (cur2 == cur1) return cur2;
//                    cur2 = cur2.next;
//                } else {
//                    if (cur1 == cur2) return cur1;
//                    cur1 = cur1.next;
//                }
//                step--;
//            }
//            //两者一起走
//            while(cur1 != null && cur2 != null) {
//                if(cur1.val == cur2.val) return cur1;
//                cur1 = cur1.next;
//                cur2 = cur2.next;
//            }
//            return null;
//        }
//    }
/**
 * 一段字符串中 找指定的子序列
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextInt()) { // 注意 while 处理多个 case
//                int n = in.nextInt();
//                char[] str = in.next().toCharArray();
//                //线性dp
//                long s = 0, h = 0,y = 0;
//                for(int i = 0; i < n; i++) {
//                    if(str[i] == 's') s += 1;
//                    if(str[i] == 'h') h += s;
//                    if(str[i] == 'y') y += h;
//                }
//                System.out.println(y);
//            }
//        }
//    }

    /**
     * 数字统计
     * @param args
     */
//    public static void main(String[] args) {
//    Scanner in = new Scanner(System.in);
//    // 注意 hasNext 和 hasNextLine 的区别
//    while (in.hasNextInt()) { // 注意 while 处理多个 case
//        int left = in.nextInt();
//        int right = in.nextInt();
//        int ret = 0;
//        for (int i = left; i <= right; i++) {
//            int tmp = i;
//            while (tmp > 0) {
//                if (tmp % 10 == 2) ret++;
//                tmp = tmp / 10;
//            }
//        }
//        System.out.println(ret);
//    }
//}

    /**
     * 两个数组的交集
     * @param nums1
     * @param nums2
     * @return
     */
//    public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
//        // write code here
//        ArrayList<Integer> ret = new ArrayList<>();
//        boolean[] hash = new boolean[10010];
//        for(int x : nums1) {
//            hash[x]  = true;
//        }
//        for(int x : nums2) {
//            if(hash[x]) {
//                ret.add(x);
//                //细节: 添加完后记得将hash表中的值删除-->置为false否则会重复加入某个数
//                hash[x] = false;
//            }
//        }
//        return ret;
//    }

    /**
     *点击消除---栈这种数据结构的使用
     * @param args
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNext()) { // 注意 while 处理多个 case
//            String s = in.next();
//            char[] ch = s.toCharArray();
//            //使用可变长数组-->StringBuffer来模拟栈
//            StringBuffer sb = new StringBuffer();
//            for (char c : ch) {
//                int len = sb.length();
//                if (len == 0) {
//                    sb.append(c);
//                    continue;
//                }
//                if (sb.charAt(len - 1) == c) {
//                    sb.deleteCharAt(len - 1);
//                } else {
//                    sb.append(c);
//                }
//            }
//            if(sb.length() == 0) {
//                System.out.println(0);
//                continue;
//            }
//            System.out.println(sb.toString());
//        }
//    }

    /**
     * 牛牛快递
     * @param args
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNextFloat()) { // 注意 while 处理多个 case
//            float a = in.nextFloat();
//            char b = in.next().charAt(0);
//            int ret = 0;
//            if (a <= 1) {
//                ret += 20;
//            } else {
//                ret += 20;
//                float tmp = a - 1;
//                if(tmp - (int)tmp > 0) {
//                    ret += (int)tmp + 1;
//                } else {
//                    ret += tmp;
//                }
//
//            }
//            if(b == 'y') ret += 5;
//            System.out.println(ret);
//        }
//    }

    /**
     *  最小花费爬楼梯
     * @param args
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNextInt()) { // 注意 while 处理多个 case
//            int n = in.nextInt();
//            int[] cost = new int[n];
//            for(int i = 0; i < n; i++) {
//                cost[i] = in.nextInt();
//            }
//            if(n == 1) {
//                System.out.println(cost[0]);
//                continue;
//            }
//            int[] dp = new int[n + 1];
//            for(int i = 2; i <= n; i++) {
//                dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
//            }
//            System.out.println(dp[n]);
//        }
//    }

    /**
     * 数组中两个字符串的最小距离
     * @param args
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNextInt()) { // 注意 while 处理多个 case
//            int n = in.nextInt();
//            String str1 = in.next();
//            String str2 = in.next();
//            String[] str = new String[n];
//            for (int i = 0; i < n; i++) {
//                str[i] = in.next();
//            }
//            int prev1 = -1;
//            int prev2 = -1;
//            int ret = 0x3f3f3f3f;
//            for (int i = 0; i < n; i++) {
//                if (str[i].equals(str1)) {
//                    prev1 = i;
//                    if (prev2 != -1) {
//                        ret = Math.min(ret, i - prev2);
//                    }
//                } else if (str[i].equals(str2)) {
//                    prev2 = i;
//                    if (prev1 != -1) {
//                        ret = Math.min(ret, i - prev1);
//                    }
//                }
//            }
//            if (ret == 0x3f3f3f3f) {
//                System.out.println(-1);
//            } else {
//                System.out.println(ret);
//            }
//        }
//    }



}
